import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/17 17:44
 * @description 递归
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] in = {9,3,15,20,7}, po = {9,15,7,20,3};
        solution.buildTree(in, po);
    }
    private Map<Integer, Integer> map;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = inorder.length;
        // 构造哈希映射，帮助找到中序遍历的根节点位置
        map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(inorder[i], i);
        }
        return myBuildTree(inorder, postorder, 0, n-1,0, n-1);
    }
    public TreeNode myBuildTree(int[] inorder, int[] postorder, int inorderLeft, int inorderRight,
                                int postorderLeft, int postorderRight) {
        if (postorderLeft > postorderRight) {
            return null;
        }

        // 在中序遍历中定位根结点，这是下标
        int inorderRoot = map.get(postorder[postorderRight]);

        // 先把根节点建立出来
        TreeNode root = new TreeNode(inorder[inorderRoot]);

        //得到左子树的结点数目
        int leftSubTreeLen =  inorderRoot - inorderLeft;

        root.left = myBuildTree(inorder, postorder, inorderLeft, inorderRoot - 1,
                postorderLeft, postorderLeft + leftSubTreeLen - 1);

        root.right = myBuildTree(inorder, postorder, inorderRoot + 1, inorderRight,
                postorderLeft + leftSubTreeLen, postorderRight - 1);

        return root;
    }
}
